﻿//using Nemerle.Collections;
using Nemerle.Text;
using Nemerle.Utility;
using Nemerle.Assertions;

using System;
using System.Collections.Generic;
using System.Linq;

namespace Nemerle.Data.NList
{
  
  public module NLists
  {
    
    #warning not tested
    public ToArray[T](
      [NotNull] this lst : list[T]
    ) : array[T]
    {
      def res = List();
      foreach(item in lst) res.Add(item);
      res.ToArray()
    }
    
    
    public ToSeq[T](
      [NotNull] this lst : list[T]
    ) : Seq[T]
    {
       foreach(elem in lst) yield elem
    }
    
    //------------------
    // Basic functions
    //------------------
    
    
    #warning not tested
    public Append[T](
      [NotNull] this lst : ReversedList[T],
                    item : T
    ) : ReversedList[T]
    {
      ReversedList(item :: lst.IgnoreOrdering())
    }
    
    
    #warning not tested
    public AppendRev[T](
      [NotNull] this lst : list[T],
                    item : T
    ) : ReversedList[T]
    {
      ReversedList(item :: lst.Rev())
    }
    
    
    #warning not tested
    public Append[T](
      [NotNull] this lst : list[T],
                    item : T
    ) : list[T]
    {
      (item :: lst.Rev()).Rev()
    }
    
    
    #warning not tested
    public Prepend[T](
      [NotNull] this lst : ReversedList[T],
                    item : T
    ) : list[T]
    {
      item :: lst.Rev()
    }
    
    
    #warning not tested
    public Prepend[T](
      [NotNull] this lst : list[T],
                    item : T
    ) : list[T]
    {
      item :: lst
    }
    
    //--------------------------
    // Sequence transformations
    //--------------------------
    
    
    public Map[From, To](
      [NotNull] this source : list[From],
      [NotNull]      f      : From -> To
    ) : list[To]
    {
      $[ f(item) | item in source ]
    }
    
    
    #warning not tested
    public MapRev[From, To](
      [NotNull] this source : list[From],
      [NotNull]      f      : From -> To
    ) : ReversedList[To]
    {
      mutable result = [];
      foreach(x in source with i)
        result ::= f(x);
      ReversedList(result)
    }
    
    
    #warning not tested
    public MapRev[From, To](
      [NotNull] this source : ReversedList[From],
      [NotNull]      f      : From -> To
    ) : list[To]
    {
      source.IgnoreOrdering().MapRev(f).IgnoreOrdering()
    }
    
    
    public MapIRev[From, To](
      [NotNull] this source : list[From],
      [NotNull]      f      : int * From -> To
    ) : ReversedList[To]
    {
      mutable result = [];
      foreach(x in source with i)
        result ::= f(i, x);
      ReversedList(result)
    }
    
    
    #warning not tested
    public MapIRev[From, To](
      [NotNull] this source : ReversedList[From],
      [NotNull]      f      : int * From -> To
    ) : list[To]
    {
      source.IgnoreOrdering().MapIRev(f).IgnoreOrdering()
    }
    
    
    public MapI[From, To](
      [NotNull] this source : list[From],
      [NotNull]      f      : int * From -> To
    ) : list[To]
    {
      source.MapIRev(f).Rev()
    }
    
    
    public IntersperseRev[T](
      [NotNull] this lst : list[T], 
               separator : T
    ) : list[T]
    {
      match(lst)
      {
        | [] => []
        | [x] => [x]
        | x :: xs => {
          def loop(src, res) {
            match(src) {
              | [] => res
              | y :: ys => loop(ys, y :: separator :: res)
            }
          }
          loop(xs, [x])
        }
      }
    }
    
    
    public Intersperse[T](
      [NotNull] this lst : list[T], 
               separator : T
    ) : list[T]
    {
      lst.IntersperseRev(separator).Rev()
    }
    
    
    public IntersperseWithRev[T](
      [NotNull] this lst : list[T], 
                     f   : T * T -> T
    ) : list[T]
    {
      match(lst)
      {
        | [] => []
        | [x] => [x]
        | x :: xs => {
          def loop(src, prev, res) {
            match(src) {
              | [] => res
              | y :: ys => loop(ys, y, y :: f(prev, y) :: res)
            }
          }
          loop(xs, x, [x])
        }
      }
    }
    
    
    public IntersperseWith[T](
      [NotNull] this lst : list[T], 
                     f   : T * T -> T
    ) : list[T]
    {
      lst.IntersperseWithRev(f).Rev()
    }
    
    
    public MapOptionRev[From, To](
      [NotNull] this source : list[From],
      [NotNull]      f      : From -> option[To]
    ) : ReversedList[To]
    {
      //$[ x | Some(x) in $[ f(y) | y in source ]]
      def loop(lst, res)
      {
        match(lst) {
          | []      => res
          | x :: xs => match(f(x)) {
            | Some(y) => loop(xs, y :: res)
            | None()  => loop(xs, res)
          }
        }
      }
      ReversedList(loop(source, []))
    }
    
    #warning not tested
    
    public MapOptionRev[From, To](
      [NotNull] this source : ReversedList[From],
      [NotNull]      f      : From -> option[To]
    ) : list[To]
    {
      source.IgnoreOrdering().MapOptionRev(f).IgnoreOrdering()
    }
    
    
    public MapOption[From, To](
      [NotNull] this source : list[From],
      [NotNull]      f      : From -> option[To]
    ) : list[To]
    {
      source.MapOptionRev(f).Rev()
    }
    
    
    public CatOptions[T](
      [NotNull] this source : list[option[T]]
    ) : list[T]
    {
      $[ x | Some(x) in source ]
    }
    
    
    #warning not tested
    public CatOptionsRev[T](
      [NotNull] this source : list[option[T]]
    ) : ReversedList[T]
    {
      mutable res = [];
      foreach(Some(x) in source) res ::= x;
      ReversedList(res)
    }
    
    
    #warning not tested
    public CatOptionsRev[T](
      [NotNull] this source : ReversedList[option[T]]
    ) : list[T]
    {
      source.IgnoreOrdering().CatOptionsRev().IgnoreOrdering()
    }
    
    
    public PairwiseWithRev[From, To](
      [NotNull] this source : list[From],
      [NotNull] f           : From * From -> To
    ) : ReversedList[To]
    {
      match(source)
      {
        | [] | _ :: [] => ReversedList([])
        | _ => {
          def loop(lst, prev, res) {
            match(lst) {
              | []      => res
              | x :: xs => loop(xs, x, f(prev, x) :: res) 
            }
          }
          ReversedList(loop(source.Tail, source.Head, []))
        }
      }
    }
    
    
    public PairwiseWith[From, To](
      [NotNull] this source : list[From],
      [NotNull] f           : From * From -> To
    ) : list[To]
    {
      source.PairwiseWithRev(f).Rev()
    }
    
    
    public PairwiseRev[T](
      [NotNull] this source : list[T]
    ) : ReversedList[T * T]
    {
      match(source)
      {
        | [] | _ :: [] => ReversedList([])
        | _ => {
          def loop(lst, prev, res) {
            match(lst) {
              | []      => res
              | x :: xs => loop(xs, x, (prev, x) :: res) 
            }
          }
          ReversedList(loop(source.Tail, source.Head, []))
        }
      }
    }
    
    
    public Pairwise[T](
      [NotNull] this source : list[T]
    ) : list[T * T]
    {
      source.PairwiseRev().Rev()
    }
    
    //-----------------------------
    // Reducing sequences (folds)
    //-----------------------------
    
    
    public Fold[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : TAccumulator * T -> TAccumulator
    ) : TAccumulator
    {
      foreach(value in lst)
        acc = f(acc, value);
      acc
    }
    
    
    public FoldRight[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : T * TAccumulator -> TAccumulator
    ) : TAccumulator
    {
      NLists.ToArray(lst).FoldRight(acc, f)
    }
    
    
    public Reduce[T](
      [NotNull] this lst : list[T],
      [NotNull] f : T * T -> T
    ) : T
    requires !lst.IsEmpty 
    {
      NLists.Fold(lst.Tail, lst.Head, f)
    }
    
    
    public ReduceRight[T](
      [NotNull] this lst : list[T],
      [NotNull] f : T * T -> T
    ) : T
    requires !lst.IsEmpty 
    {
      NLists.ToArray(lst).ReduceRight(f)
    }
    
    
    public FoldI[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : int * TAccumulator * T -> TAccumulator
    ) : TAccumulator
    {
      foreach (value in lst with i)
        acc = f(i, acc, value);
      acc
    }
    
    
    public FoldRightI[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : int * T * TAccumulator -> TAccumulator
    ) : TAccumulator
    {
      NLists.ToArray(lst).FoldRightI(acc, f)
    }
    
    
    public Concatenate[T](
      [NotNull] this lists : list[list[T]],
    ) : list[T]
    {
      $[ item | items in lists, item in items ]
    }
    
    
    public ConcatMap[From, To](
      [NotNull] this lst : list[From],
      [NotNull] f        : From -> list[To]
    ) : list[To]
    {
      $[ item | x in lst, item in f(x) ]
    }
    
    
    public Exist[T](
      [NotNull] this lst : list[T],
      [NotNull] f        : T -> bool
    ) : bool
    {
      exit : {
       foreach(elem in lst)
         when(f(elem)) exit(true);
       false
      }
    }
    
    
    public ForAll[T](
      [NotNull] this lst : list[T],
      [NotNull] f        : T -> bool
    ) : bool
    {
      exit : {
       foreach(elem in lst)
         unless(f(elem)) exit(false);
       true
      }
    }
    
    
    public Or(
      [NotNull] this lst : list[bool],
    ) : bool
    {
      exit : {
       foreach(elem in lst)
         when(elem) exit(true);
       false
      }
    }
    
    
    public And(
      [NotNull] this lst : list[bool],
    ) : bool
    {
      exit : {
       foreach(elem in lst)
         unless(elem) exit(false);
       true
      }
    }
    
    
    public Maximum[T](
      [NotNull] this lst : list[T]
    ) : T
    where T : IComparable[T]
    requires !lst.IsEmpty
    {
      mutable res = lst.Head;
      foreach(elem in lst.Tail)
        when(elem.CompareTo(res) > 0) res = elem;
      res
    }
    
    
    public MaximumBy[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K
    ) : T
    where K : IComparable[K]
    requires !lst.IsEmpty
    {
      mutable res = lst.Head;
      mutable key = selector(res);
      foreach(elem in lst.Tail)
        when(selector(elem).CompareTo(key) > 0)
        {
          res = elem;
          key = selector(res);
        };
      res
    }
    
    
    public MaximumsByRev[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K
    ) : ReversedList[T]
    where K : IComparable[K]
    {
      if(!lst.IsEmpty)
      {
        mutable res = [lst.Head];
        mutable key = selector(lst.Head);
        
        foreach(elem in lst.Tail)
        {
          def cmp = selector(elem).CompareTo(key);
          when(cmp > 0) res = [];
          unless(cmp < 0)
          {
            res ::= elem; 
            key = selector(elem);
          }
        };
        
        ReversedList(res)
      }
      else
        ReversedList([])
    }
    
    #warning not tested
    public MaximumsByRev[T, K](
      [NotNull] this lst : ReversedList[T],
      [NotNull] selector : T -> K
    ) : list[T]
    where K : IComparable[K]
    {
      lst.AsIs().MaximumsByRev(selector).AsIs()
    }
    
    
    public MaximumsBy[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K
    ) : list[T]
    where K : IComparable[K]
    {
      lst.MaximumsByRev(selector).Rev()
    }
    
    
    public Minimum[T](
      [NotNull] this lst : list[T]
    ) : T
    where T : IComparable[T]
    requires !lst.IsEmpty
    {
      mutable res = lst.Head;
      foreach(elem in lst.Tail)
        when(elem.CompareTo(res) < 0) res = elem;
      res
    }
    
    
    public MinimumBy[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K
    ) : T
    where K : IComparable[K]
    requires !lst.IsEmpty
    {
      mutable res = lst.Head;
      mutable key = selector(res);
      foreach(elem in lst.Tail)
        when(selector(elem).CompareTo(key) < 0)
        {
          res = elem;
          key = selector(res);
        };
      res
    }
    
    
    public MinimumsByRev[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K
    ) : ReversedList[T]
    where K : IComparable[K]
    {
      if(!lst.IsEmpty)
      {
        mutable res = [lst.Head];
        mutable key = selector(lst.Head);
        
        foreach(elem in lst.Tail)
        {
          def cmp = selector(elem).CompareTo(key);
          when(cmp < 0) res = [];
          unless(cmp > 0)
          {
            res ::= elem; 
            key = selector(elem);
          }
        };
        
        ReversedList(res)
      }
      else
        ReversedList([])
    }
    
    #warning not tested
    public MinimumsByRev[T, K](
      [NotNull] this lst : ReversedList[T],
      [NotNull] selector : T -> K
    ) : list[T]
    where K : IComparable[K]
    {
      lst.AsIs().MinimumsByRev(selector).AsIs() 
    }
    
    public MinimumsBy[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K
    ) : list[T]
    where K : IComparable[K]
    {
      lst.MinimumsByRev(selector).Rev() 
    }
    
    //=================
    // Building lists
    //=================
    //--------
    // Scans
    //--------
    
    
    public ScanRev[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : TAccumulator * T -> TAccumulator
    ) : list[TAccumulator]
    {
      mutable result = [acc];
      foreach (value in lst)
      {
        acc = f(acc, value);
        result ::= acc;
      }
      result
    }
    
    
    public Scan[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : TAccumulator * T -> TAccumulator
    ) : list[TAccumulator]
    {
      lst.ScanRev(acc,f).Rev()
    }
    
    
    public Scan'[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : TAccumulator * T -> TAccumulator
    ) : list[TAccumulator]
    {
      mutable result = List();
      result.Add(acc);
      foreach (value in lst)
      {
        acc = f(acc, value);
        result.Add(acc);
      }
      result.ToArray().ToNList()
    }
    
    
    public ScanRight[TAccumulator, T](
      [NotNull] this lst : list[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : T * TAccumulator -> TAccumulator
    ) : list[TAccumulator]
    {
      NLists.ToArray(lst).ScanRight(acc, f).ToNList()
    }
    
    //--------------------
    // Accumulating maps
    //--------------------
    
    
    public MapAccRev[TAcc, T, R](
      [NotNull] this lst : list[T],
      mutable        acc : TAcc,
      [NotNull]      f   : (TAcc * T) -> (TAcc * R)
    ) : TAcc * list[R]
    {
      def loop(l, a, r) {
        match(l) {
          | []      => (a, r)
          | x :: xs => { def (a', x') = f(a, x); loop(xs, a', x' :: r)} 
        }
      }
      loop(lst, acc, [])
    }
    
    
    public MapAcc[TAcc, T, R](
      [NotNull] this lst : list[T],
      mutable        acc : TAcc,
      [NotNull]      f   : (TAcc * T) -> (TAcc * R)
    ) : TAcc * list[R]
    {
      def (a, r) = lst.MapAccRev(acc, f);
      (a, r.Rev())
    }
    
    
    public MapAccRight[TAcc, T, R](
      [NotNull] this lst : list[T],
      mutable        acc : TAcc,
      [NotNull]      f   : (TAcc * T) -> (TAcc * R)
    ) : TAcc * list[R]
    {
      def(a, res) = NLists.ToArray(lst).MapAccRight(acc, f);
      (a, res.ToNList())
    }
    
    //------------
    // Unfolding
    //------------
    
    
    public Replicate[T](item : T, times : int) : list[T]
    {
      def loop(i, r) {
        if (i > 0) loop(i - 1, item :: r) else r
      }
      loop(times, [])
    }
    
    public ReplicateResultRev[T](f : void -> T, times : int) : list[T]
    {
      def loop(i, r) {
        if (i > 0) loop(i - 1, f() :: r) else r
      }
      loop(times, [])
    }
    
    public ReplicateResult[T](f : void -> T, times : int) : list[T]
    {
      ReplicateResultRev(f, times).Rev()
    }
    
    public Unfold[TState, T](
      mutable   init : TState,
      [NotNull] f    : TState -> option[TState * T]
    ) : list[T]
    {
      NLists.UnfoldRight(init, f).Rev()
    }
    
    
    public UnfoldRight[TState, T](
      mutable   init : TState,
      [NotNull] f    : TState -> option[TState * T]
    ) : list[T]
    {
      def loop(state, res) {
        match(state) {
          | Some((s, r)) => loop(f(s), r :: res)
          | None => res
        }
      }
      loop(f(init), [])
    }
    
     //===========
    // Subarrays
    //===========
    //----------------------
    // Extracting subarrays
    //----------------------
    
    #warning not tested
    public TakeAtMost'''[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      def loop(l, i, res) {
        match(l) {
          | x :: xs when i >= 0 => loop(xs, i - 1, x :: res) 
          | _                  => res
        }
      }
      loop(lst, n, []).Rev()
    }
    
    public TakeAtMost'[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      //def res = List();
      mutable res = [];
      exit : {
       foreach(item in lst with i)
         if(i > n) exit() else res ::= item; //res.Add(item);
      }
      //$[ x | x in res]
      res.Rev()
    }
    
    public GetRev[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      def loop(l, i, res) {
        match(l) {
          | x :: xs when i > 0 => loop(xs, i - 1, x :: res) 
          | _                  => res
        }
      }
      loop(lst, n, [])
    }
    
    public Get[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      lst.GetRev(n).Rev()
    }
    
    public GetExactly[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      //def loop(l, i, res) {
      //  match(l) {
      //    | []      when i >= -1 => res
      //    | x :: xs when i >= 0  => loop(xs, i - 1, x :: res) 
      //    | _                    => throw ArgumentException()
      //  }
      //}
      //loop(lst, n, []).Rev()
      def res = array(n);
      mutable j = 0;
      exit : {
       foreach(item in lst)
       {
         if(j < n) res[j] = item else exit();
         j++;
       }
      }
      if(j == n)
        res.TakeToNList(j)
      else
        throw ArgumentException("list.Length < n")
    }
    
    
    public DropExactly[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      def loop(l, i) {
        match(l) {
          | []      when i >= 0 => []
          | []                  => throw ArgumentException("lst.Length < n")
          | _ :: xs when i > 0  => loop(xs, i - 1) 
          | _                   => l
        }
      }
      loop(lst, n)
    }
    
    
    public Drop[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      lst.DropAtMost(n)
    }
    
    
    public DropAtMost[T](
      [NotNull] this lst : list[T],
      n : int
    ) : list[T]
    {
      def loop(l, i) {
        match(l) {
          | []                  => []
          | _ :: xs when i > 0  => loop(xs, i - 1) 
          | _                   => l
        }
      }
      loop(lst, n)
    }
    
    
    public DropWhile[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T]
    {
      def loop(l) {
          | []                    => []
          | x :: xs when pred(x)  => loop(xs)
          | _                     => l
      }
      loop(lst)
    }

    
    public GetWhileRev[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T]
    {
      def loop(l, res) {
        match(l) {
          | x :: xs when pred(x) => loop(xs, x :: res) 
          | _                    => res
        }
      }
      loop(lst, [])
    }
    
    
    public GetWhile[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T]
    {
      lst.GetWhileRev(pred).Rev()
    }
    
    
    public SplitExactlyAtRev[T](
      [NotNull] this lst : list[T],
                     n   : int
    ) : list[T] * list[T]
    requires n >= 0
    {
      def loop(r, i, l) {
        match(l) {
          | [] when i >= 0     => (r, [])
          | []                 => throw ArgumentException("lst.Length < n")
          | x :: xs when i > 0 => loop(x :: r, i - 1, xs)
          | _                  => (r, l)
        }
      }
      loop([], n, lst)
    }
    
    
    public SplitExactlyAt[T](
      [NotNull] this lst : list[T],
                     n   : int
    ) : list[T] * list[T]
    {
      def (l, r) = lst.SplitExactlyAtRev(n);
      (l.Rev(), r)
    }
    
    
    public SplitAtRev[T](
      [NotNull] this lst : list[T],
                     n   : int
    ) : list[T] * list[T]
    {
      def loop(r, i, l) {
        match(l) {
          | []                 => (r, [])
          | x :: xs when i > 0 => loop(x :: r, i - 1, xs)
          | _                  => (r, l)
        }
      }
      loop([], n, lst)
    }
    
    
    public SplitAt[T](
      [NotNull] this lst : list[T],
                     n   : int
    ) : list[T] * list[T]
    {
      def (l, r) = lst.SplitAtRev(n);
      (l.Rev(), r)
    }
    
    
    public SpanRev[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T] * list[T]
    {
      def loop(l, res) {
        match(l) {
          | []                    => (res, [])
          | x :: xs when pred(x)  => loop(xs, x :: res)
          | _                     => (res, l)
        }
      }
      loop(lst, [])
    }
    
    
    public Span[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T] * list[T]
    {
      def(l, r) = lst.SpanRev(pred);
      (l.Rev(), r)
    }
    
    
    public BreakRev[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T] * list[T]
    {
      def loop(l, res) {
        match(l) {
          | []                     => (res, [])
          | x :: xs when !pred(x)  => loop(xs, x :: res)
          | _                      => (res, l)
        }
      }
      loop(lst, [])
    }
    
    
    public Break[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T] * list[T]
    {
      def(l, r) = lst.BreakRev(pred);
      (l.Rev(), r)
    }
    
    #warning TO DO
    
    public Inits[T](
      [NotNull] this lst : list[T]
    ) : list[list[T]]
    {
      def len = lst.Length;
      def result = array(len + 1);
      foreach(i in [0 .. result.Length - 1])
        result[i] = lst.GetExactly(i);
      result.ToNList()
    }
    
    
    public TailsRev[T](
      [NotNull] this lst : list[T]
    ) : list[list[T]]
    {
      def loop(l, res) {
        match(l) {
          | []      => [] :: res
          | _ :: xs => loop(xs, xs :: res)
        }
      }
      loop(lst, [lst])
    }
    
    
    public Tails[T](
      [NotNull] this lst : list[T]
    ) : list[list[T]]
    {
      lst.TailsRev().Rev()
    }
    
    //-------------
    // Predicates
    //-------------
    
    //==================
    // Searching lists
    //==================
    //------------------------
    // Searching by equality
    //------------------------
    
    
    public ContainsElem[T](
      [NotNull] this lst : list[T],
      elem : T
    ) : bool
    {
      def cmp = EqualityComparer.Default;
      exit : {
       foreach(x in lst)
         when(cmp.Equals(x,elem)) exit(true);
       false
      }
    }
    
    
    public ElementOf[T](
      this elem : T,
      [NotNull] lst : list[T]
    ) : bool
    {
      lst.ContainsElem(elem) 
    }
    
    //----------------------------
    // Searching with a predicate
    //----------------------------
    
    
    public Find[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : option[T]
    where T : IEquatable[T]
    {
      exit : {
       foreach(x in lst)
         when(pred(x)) exit(Some(x));
       None()
      }
    }
    
    
    public Filter[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T]
    {
      $[ x | x in lst, pred(x) ]
    }
    
    public FilterRev[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : ReversedList[T]
    {
      mutable result = [];
      foreach(x when pred(x) in lst)
         result ::= x;
      ReversedList(result)
    }

    public FilterRev[T](
      [NotNull] this lst : ReversedList[T],
      [NotNull]     pred : T -> bool
    ) : list[T]
    {
      lst.IgnoreOrdering().FilterRev(pred).IgnoreOrdering()
    }    
    
    public FilterIRev[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : int * T -> bool //TO DO подумать над тем, стоит ли использовать порядок парметров IterI или LINQ 
    ) : ReversedList[T]
    {
      mutable result = [];
      foreach(x when pred(i, x) in lst with i)
         result ::= x;
      ReversedList(result)
    }
    
    #warning not tested
    public FilterIRev[T](
      [NotNull] this lst : ReversedList[T],
      [NotNull]     pred : int * T -> bool //TO DO подумать над тем, стоит ли использовать порядок парметров IterI или LINQ 
    ) : list[T]
    {
      lst.IgnoreOrdering().FilterIRev(pred).IgnoreOrdering()
    }
    
    public FilterI[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : int * T -> bool //TO DO подумать над тем, стоит ли использовать порядок парметров IterI или LINQ 
    ) : list[T]
    {
      lst.FilterIRev(pred).Rev()
    }
    
    
    public PartitionRev[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T] * list[T]
    {
      mutable res1 = [];
      mutable res2 = [];
      foreach(x in lst)
        if (pred(x))
         res1 ::= x;
        else
         res2 ::= x;
      (res1, res2)
    }
    
    
    public Partition[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T] * list[T]
    {
      def(l,r) = lst.PartitionRev(pred);
      (l.Rev(), r.Rev())
    }
    
    //-----------
    // Indexing
    //-----------
    
    
    public Nth[T](
      [NotNull] this lst : list[T],
                       n : int
    ) : option[T]
    {
      exit : {
       foreach(x in lst with i)
         when(i == n) exit(Some(x));
       None()
      }
    }
    
    
    public IndexOf[T](
      [NotNull] this lst : list[T],
                    elem : T
    ) : option[int]
    {
      def cmp = EqualityComparer.Default;
      exit : {
       foreach(x in lst with i)
         when(cmp.Equals(x,elem)) exit(Some(i));
       None()
      }
    }
    
    
    public IndicesOfRev[T](
      [NotNull] this lst : list[T],
                    elem : T
    ) : ReversedList[int]
    {
      def cmp = EqualityComparer.Default;
      mutable result = [];
      foreach(x when cmp.Equals(x,elem) in lst with i)
         result ::= i;
      ReversedList(result)
    }
    
    
    public IndicesOf[T](
      [NotNull] this lst : list[T],
                    elem : T
    ) : list[int]
    {
      lst.IndicesOfRev(elem).Rev()
    }
    
    
    public InsertAt[T](
      [NotNull] this lst : list[T],
                    item : T,
                       n : int
    ) : list[T]
    {
      def loop(l, i, res) {
        match(l) {
          | []      when i == n => (item :: res).Rev()
          | []                  => res.Rev()
          | x :: xs when i == n => copy(x :: item :: res, xs)
          | x :: xs             => loop(xs, i + 1, x :: res)
        }
      }
      and copy(l, res) {
        match(l) {
          | []      => res
          | x :: xs => copy(xs, x :: res)
        }
      }
      loop(lst, 0, [])
    }
    
    
    public InsertExactlyAt[T](
      [NotNull] this lst : list[T],
                    item : T,
                       n : int
    ) : list[T]
    requires n >= 0
    {
      def loop(l, i, res) {
        match(l) {
          | []      when i == n => (item :: res).Rev()
          | []                  => throw ArgumentException("lst.Length + 1 < n")
          | x :: xs when i == n => copy(x :: item :: res, xs)
          | x :: xs             => loop(xs, i + 1, x :: res)
        }
      }
      and copy(l, res) {
        match(l) {
          | []      => res
          | x :: xs => copy(xs, x :: res)
        }
      }
      loop(lst, 0, [])
    }
    
    //-------------------------------
    // Zipping and unzipping lists
    //-------------------------------
    
    
    public ZipWithRev[From1, From2, To](
      [NotNull] this lst1 : list[From1],
      [NotNull]      lst2 : list[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : ReversedList[To]
    {
      def loop(l1, l2, res){
        match(l1, l2) {
          | ([], _) | (_, [])  => res
          | (x :: xs, y :: ys) => loop(xs, ys, f(x, y) :: res)
        }
      }
      ReversedList(loop(lst1, lst2, []))
    }
    
    
    public ZipWith[From1, From2, To](
      [NotNull] this lst1 : list[From1],
      [NotNull]      lst2 : list[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : list[To]
    {
      lst1.ZipWithRev(lst2, f).Rev()
    }
    
    
    public ZipRev[T1, T2](
      [NotNull] this lst1 : list[T1],
      [NotNull]      lst2 : list[T2],
    ) : list[T1*T2]
    {
      def loop(l1, l2, res){
        match(l1, l2) {
          | ([], _) | (_, [])  => res
          | (x :: xs, y :: ys) => loop(xs, ys, (x, y) :: res)
        }
      }
      loop(lst1, lst2, [])
    }
    
    
    public Zip[T1, T2](
      [NotNull] this lst1 : list[T1],
      [NotNull]      lst2 : list[T2],
    ) : list[T1*T2]
    {
      lst1.ZipRev(lst2).Rev()
    }
    
    
    public Map2Rev[From1, From2, To](
      [NotNull] this lst1 : list[From1],
      [NotNull]      lst2 : list[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : list[To]
    {
      def loop(l1, l2, res){
        match(l1, l2) {
          | ([], [])           => res
          | ([], _) | (_, [])  => throw ArgumentException("lst1.Length != lst2.Length")
          | (x :: xs, y :: ys) => loop(xs, ys, f(x, y) :: res)
        }
      }
      loop(lst1, lst2, [])
    }
    
    
    public Map2[From1, From2, To](
      [NotNull] this lst1 : list[From1],
      [NotNull]      lst2 : list[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : list[To]
    {
      lst1.Map2Rev(lst2, f).Rev()
    }
    
    
    public UnZipRev[T1, T2](
      [NotNull] this lst : list[T1*T2]
    ) : list[T1] * list[T2]
    {
      mutable res1 = [];
      mutable res2 = [];
      foreach(x in lst)
      {
         res1 ::= x[0];
         res2 ::= x[1];
      }
      (res1, res2)
    }
    
    
    public UnZip[T1, T2](
      [NotNull] this lst : list[T1*T2]
    ) : list[T1] * list[T2]
    {
      def (l, r) = lst.UnZipRev();
      (l.Rev(), r.Rev())
    }
    
    
    public Firsts[T1, T2](
      [NotNull] this lst : list[T1*T2]
    ) : list[T1]
    {
      $[ x | (x, _) in lst ]
    }
    
    
    #warning not tested
    public FirstsRev[T1, T2](
      [NotNull] this lst : list[T1*T2]
    ) : list[T1]
    {
      mutable result = [];
      foreach((x,_) in lst)
        result ::= x;
      result
    }
    
    
    public Seconds[T1, T2](
      [NotNull] this lst : list[T1*T2]
    ) : list[T2]
    {
      $[ x | (_, x) in lst ]
    }
    
    
    #warning not tested
    public SecondsRev[T1, T2](
      [NotNull] this lst : list[T1*T2]
    ) : list[T2]
    {
      mutable result = [];
      foreach((_,x) in lst)
        result ::= x;
      result
    }
    
    //------------------
    // "Set" operations
    //------------------
    
    #warning not tested
    
    public UniqueElements[T](
      [NotNull] this lst : list[T]
    ) : list[T]
    {
      Essence(lst)
    }

    
    public Essence[T](
      [NotNull] this lst : list[T]
    ) : list[T]
    {
      def set = HashSet(lst);
      set.ToArray().ToNList()
    }

    
    public EssenceBy[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K 
    ) : list[T]
    {
      def set = HashSet(lst, SelectEqComparer(selector));
      set.ToArray().ToNList()
    }
    
    
    public DeleteFirst[T](
      [NotNull] this lst : list[T],
      elem : T
    ) : list[T]
    {
      def cmp = EqualityComparer.Default;
      def loop(l, r) {
        match(l) {
          | []                              => r.Rev()
          | x :: xs when cmp.Equals(x,elem) => copy(r, xs)
          | x :: xs                         => loop(xs, x :: r)
        }
      }
      and copy(l, r) {
        match(l) {
          | [] => r
          | x :: xs => copy(xs, x :: r)
        }
      }
      loop(lst, [])
    }
    
    #warning not tested
    public DeleteFirstBy[T, K](
      [NotNull] this lst : list[T],
                     key : K,
      [NotNull] selector : T -> K
    ) : list[T]
    {
      def cmp = EqualityComparer.Default;
      def loop(l, r) {
        match(l) {
          | []                              => r.Rev()
          | x :: xs when cmp.Equals(key, selector(x)) => copy(r, xs)
          | x :: xs                         => loop(xs, x :: r)
        }
      }
      and copy(l, r) {
        match(l) {
          | [] => r
          | x :: xs => copy(xs, x :: r)
        }
      }
      loop(lst, [])
    }
    
    #warning not tested
    
    public DeleteAll[T](
      [NotNull] this lst : list[T],
      elem : T
    ) : list[T]
    {
      def cmp = EqualityComparer.Default;
      def loop(l, r) {
        match(l) {
          | []                              => r
          | x :: xs when cmp.Equals(x,elem) => loop(xs, r)
          | x :: xs                         => loop(xs, x :: r)
        }
      }
      loop(lst, []).Rev()
    }
    
    
    public DeleteFirstWhen[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T]
    {
      def loop(l, r) {
        match(l) {
          | []                   => r.Rev()
          | x :: xs when pred(x) => copy(r, xs)
          | x :: xs              => loop(xs, x :: r)
        }
      }
      and copy(l, r) {
        match(l) {
          | []      => r
          | x :: xs => copy(xs, x :: r)
        }
      }
      loop(lst, [])
    }
    
    #warning not tested
    
    public DeleteAllBy[T](
      [NotNull] this lst : list[T],
      [NotNull]     pred : T -> bool
    ) : list[T]
    {
      def loop(l, r) {
        match(l) {
          | []                   => r
          | x :: xs when pred(x) => loop(xs, r)
          | x :: xs              => loop(xs, x :: r)
        }
      }
      loop(lst, []).Rev()
    }
    
    
    public DeleteFirsts[T](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T]
    ) : list[T]
    {
       lst1.Diff(lst2)
    }
    
    
    public Diff[T](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T]
    ) : list[T]
    {
       def set = HashSet(lst2);
       $[ x | x in lst1, !set.Contains(x) ]
    }
    
    
    public DiffBy[T, K](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T],
      [NotNull] selector : T -> K 
    ) : list[T]
    {
      def set = HashSet(lst2, SelectEqComparer(selector));
      $[ x | x in lst1, !set.Contains(x) ]
    }
    
    
    public DeleteFirstsBy[T, K](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T],
      [NotNull] selector : T -> K 
    ) : list[T]
    {
      lst1.DiffBy(lst2, selector)
    }
    
    
    public SetDiff[T](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T] 
    ) : list[T]
    {
      def set = HashSet(lst1);
      set.ExceptWith(lst2);
      set.ToArray().ToNList()
    }
    
    
    public SetDiffBy[T, K](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T],
      [NotNull] selector : T -> K 
    ) : list[T]
    {
      def set = HashSet(lst1, SelectEqComparer(selector));
      set.ExceptWith(lst2);
      set.ToArray().ToNList()
    }
    
    
    public SetAdd[T](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T]
    ) : list[T]
    {
       def set = HashSet(lst1);
       set.UnionWith(lst2);
       set.ToArray().ToNList()
    }
    
    
    public SetAddBy[T, K](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T],
      [NotNull] selector : T -> K 
    ) : list[T]
    {
      def set = HashSet(lst1, SelectEqComparer(selector));
      set.UnionWith(lst2);
      set.ToArray().ToNList();
    }    
    
    
    public Intersection[T](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T]
    ) : list[T]
    {
       def set = HashSet(lst1);
       set.IntersectWith(lst2);
       set.ToArray().ToNList()
    }
    
    
    public IntersectionBy[T, K](
      [NotNull] this lst1 : list[T],
      [NotNull]      lst2 : list[T],
      [NotNull] selector : T -> K 
    ) : list[T]
    {
      def set = HashSet(lst1, SelectEqComparer(selector));
      set.IntersectWith(lst2);
      set.ToArray().ToNList()
    }
    
    //---------------
    // Ordered lists
    //---------------
    
    
    public Sort[T](
      [NotNull] this lst : list[T]
    ) : list[T]
    where T : IComparable[T]
    {
      NLists.ToArray(lst).SortInplace().ToNList()
    }
    
    
    public Sort[T](
      [NotNull] this lst : list[T],
      [NotNull]  compare : IComparer[T] 
    ) : list[T]
    {
      NLists.ToArray(lst).SortInplace(compare).ToNList()
    }

    
    public Sort[T](
      [NotNull] this lst : list[T],
      [NotNull]  compare : T * T -> int 
    ) : list[T]
    {
      NLists.ToArray(lst).SortInplace(compare).ToNList()
    }
    
    
    public SortBy[T, K](
      [NotNull] this lst : list[T],
      [NotNull] selector : T -> K 
    ) : list[T]
    where K : IComparable[K]
    {
      NLists.ToArray(lst).SortInplaceBy(selector).ToNList()
    }

    
    public Insert[T](
      [NotNull] this lst : list[T],
                    item : T
    ) : list[T]
    where T : IComparable[T]
    {
      def loop(l, res) {
        match(l) {
          | []                                 => (item :: res).Rev()
          | x :: xs when x.CompareTo(item) > 0 => copy(x :: item :: res, xs)
          | x :: xs                            => loop(xs, x :: res)
        }
      }
      and copy(l, res) {
        match(l) {
          | []      => res
          | x :: xs => copy(xs, x :: res)
        }
      }
      loop(lst, [])
    }
    
    
    public InsertBy[T, K](
      [NotNull] this lst : list[T],
                    item : T,
                selector : T -> K
    ) : list[T]
    where K : IComparable[K]
    {
      def key = selector(item);
      def loop(l, res) {
        match(l) {
          | []                                          => (item :: res).Rev()
          | x :: xs when selector(x).CompareTo(key) > 0 => copy(x :: item :: res, xs)
          | x :: xs                                     => loop(xs, x :: res)
        }
      }
      and copy(l, res) {
        match(l) {
          | []      => res
          | x :: xs => copy(xs, x :: res)
        }
      }
      loop(lst, [])
    }
  }
  
  #warning not tested
  
  public class ListBuilder[T]
  {
    _multiplier = 2;
    mutable _count : int;
    [Accessor] mutable _blocks : list[array[T]] /*= []*/;
    mutable _initCapacity = 8;
    mutable _currentBlock : array[T] /*= array(_initCapacity)*/;
    mutable _cursor = (-1);
    mutable _currentBlockCapacity : int = _initCapacity;
    
    public Count : int
    {
      get { _count + _cursor } 
    }
    
    public this(block : array[T], blocks : list[array[T]], cursor = 0, multiplier = 2)
    {
       _currentBlock = block;
       _blocks = blocks;
       _currentBlockCapacity = block.Length;
       _cursor = cursor;
       _multiplier = multiplier;
    }
    
    public this(block : array[T], cursor = 0, multiplier = 2)
    {
      this(block, [], cursor, multiplier)
    }
    
    public this(capacity = 8, multiplier = 2)
    {
      this(array(capacity), [], 0, multiplier)
    }
    
    public Add(item : T) : void
    {
      _cursor++;
      when(_cursor == _currentBlockCapacity)
      {
        _blocks ::= _currentBlock;
        _count += _currentBlockCapacity;
        _currentBlockCapacity *= _multiplier;
        _currentBlock = array(_currentBlockCapacity);
        _cursor = 0;
      }
      _currentBlock[_cursor] = item;
    }
    
    public Append(item : T) : ListBuilder[T]
    {
      Add(item); this 
    }
    
    public ToNList() : list[T]
    {
      mutable res = [];
      foreach(i in [_cursor, _cursor - 1 .. 0]) res ::= _currentBlock[i];
      foreach(block in _blocks)
        foreach(i in [block.Length-1, block.Length-2 .. 0])
          res ::= block[i];
      res
    }
  }
  
  public interface IReversible[T]
  {
    Rev() : T
  }
  
  // контейнер обозначающий "направление" списка - можно перегрузить функции и проверять сохранение направления автоматически.
  // maprev :: list -> reversed, maprev :: reversed -> list, rev :: reversed -> list, ignoreOrder :: reversed -> list
  
  [Record]
  public class ReversedList[T] : IEnumerable[T]
  {
    _lst : list[T];
    public Rev() : list[T] { _lst.Rev() }
    public IgnoreOrdering() : list[T] { _lst }
    public AsIs() : list[T] { _lst }
    
    public GetEnumerator() : IEnumerator[T]
    {
      Rev().GetEnumerator()
    }
  }
}
